package code.commonAlgorithm;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @author cuihaoran
 * @date 2024/12/17
 */
public class ReversePolish {
    /*
    ①表达式 → 逆波兰表达式 （本算法）

    ②表达式 → 计算结果 （基本计算器）
      使用两个栈，一个op，还有一个num，存操作数。
      不要StringBuilder，全换成取操作数计算。
     */
    public String getReversePolish(String s) {
        // 去除空格
        s = s.replace(" ", "");
        int len = s.length();
        // 处理负号，思路是把-a变成0-a
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '-' && (i == 0 || s.charAt(i - 1) == '(')) {
                sb.append(0);
            }
            sb.append(c);
        }
        s = sb.toString();
        len = s.length();
        sb = new StringBuilder();
        Deque<Character> op = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            // 如果是数字，加入结果（对于逆波兰表达式，默认只有一位数字）
            if (Character.isDigit(c)) {
                // int pos = i + 1;
                // while (Character.isDigit(s.charAt(pos))) {
                //     sb.append(c);
                //     pos++;
                // }
                // i = pos - 1;
                sb.append(c);
            }
            // 如果是左括号，入栈
            else if (c == '(') {
                op.push(c);
            }
            // 如果是右括号，出栈
            else if (c == ')') {
                while (!op.isEmpty() && op.peek() != '(') {
                    sb.append(op.pop());
                }
                op.pop();
            }
            // 如果是运算符
            else {
                while (!op.isEmpty() && op.peek() != '(') {
                    if (priority(op.peek()) >= priority(c))
                        sb.append(op.pop());
                    else
                        break;
                }
                op.push(c);
            }
        }
        while (!op.isEmpty()) {
            sb.append(op.pop());
        }
        return sb.toString();
    }

    private int priority(char c) {
        if (c == '+' || c == '-')
            return 1;
        else if (c == '*' || c == '/')
            return 2;
        else
            return -1;
    }

    public static void main(String[] args) {
        ReversePolish reversePolish = new ReversePolish();
        System.out.println(reversePolish.getReversePolish("(1+2*3*4+5*6)"));
        // System.out.println(reversePolish.getReversePolish("-3+4-(-3+3+(3-1))"));
    }
}
